/**
 * // Definition for a _Node.
 * function _Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {_Node} head
 * @return {_Node}
 */
var copyRandomList = function (head) {
  if (!head) return null

  //定义哈希表
  let map = new Map()

  //第一遍:创建所有节点
  let curr = head
  while (curr) {
    map.set(curr, new _Node(curr.val))//指针->节点
    curr = curr.next
  }

  //第二遍:连接所有next和random
  curr = head
  while (curr) {
    map.get(curr).next = map.get(curr.next) || null
    map.get(curr).random = map.get(curr.random) || null
    curr = curr.next
  }

  //返回新链表的头节点
  return map.get(head)
};